package leetcode.code167.TwoSumII;

/**
 * ���Կɲ���һ�����ݹ��˾������ˣ����Զ��
 * @author Administrator
 *
 */
public class Solution2 implements ITwoSumII {

	@Override
	public int[] twoSum(int[] numbers, int target) {
		int len = numbers.length;
		int l = 0;
		int r = len - 1;
		int half = (target + 1) / 2;
		int midIndex = binarySearch(numbers, l, r, half, false);
		// �����������һ��
		if (midIndex + 1 < len && numbers[midIndex + 1] == numbers[midIndex])
			midIndex++;
		if (midIndex <= len - midIndex) {
			// ���������Ҳ����,�����С��
			return findResult(numbers, target, 0, midIndex, midIndex, len - 1);
		} else {
			int[] result = findResult(numbers, target, midIndex, len, 0, midIndex - 1);
			return new int[] { result[1], result[0] };
		}
	}

	public int[] findResult(int[] numbers, int target, int loopstart, int loopend, int bsstart, int bsend) {
		for (int i = loopstart; i < loopend; i++) {
			int myTarget = target - numbers[i];
			Integer index = this.binarySearch(numbers, bsstart, bsend, myTarget, true);
			if (index != null)
				return new int[] { i + 1, index + 1 };
		}
		return new int[] { -1, -1 };
	}

	/**
	 * @param numbers
	 * @param l
	 * @param r
	 * @param target
	 * @param nullAble true�Ǳ����ҵ���false���ҵ����������±�
	 * @return
	 */
	public Integer binarySearch(int[] numbers, int l, int r, int target, boolean nullAble) {
		int ans = r;
		while (l <= r) {
//			int mid = (r - l) % 2 == 0 ? ((r - l) / 2 + l) : ((r - l) / 2 + l) + 1;
			int mid = (r - l) / 2 + l;
			if (numbers[mid] == target) {
				return mid;
			}
			if (numbers[mid] > target) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		if (nullAble)
			return null;
		return ans;
	}

	private void debug(int[] numbers, int target) {
		ITwoSumII its = new Solution2();
		int[] result = its.twoSum(numbers, target);
		System.out.println(result[0] + "," + result[1]);
	}

	public void debug1() {
//		���룺numbers = [2,7,11,15], target = 9
//		�����[1,2]
//		���ͣ�2 �� 7 ֮�͵���Ŀ���� 9 ����� index1 = 1, index2 = 2 ��
		int[] numbers = { 2, 7, 11, 15 };
		int target = 9;
		System.out.println("[1,2]");
		this.debug(numbers, target);
	}

	public void debug2() {
//		���룺numbers = [2,3,4], target = 6
//		�����[1,3]
		int[] numbers = { 2, 3, 4 };
		int target = 6;
		System.out.println("[1,3]");
		this.debug(numbers, target);
	}

	public void debug3() {
//		���룺numbers = [-1,0], target = -1
//		�����[1,2]
		int[] numbers = { -1, 0 };
		int target = -1;
		System.out.println("[1,2]");
		this.debug(numbers, target);
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		so.debug4();

		so.debug1();
		so.debug2();
		so.debug3();
		so.debug5();
		so.debug6();
	}

	public void debug4() {
		int[] numbers = new int[] { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10 };
		int target = 11 / 2;
		int ans = this.binarySearch(numbers, 0, numbers.length - 1, target, false);
		System.out.println(ans);
	}

	public void debug5() {
		int[] numbers = { 5, 25, 75 };
		int target = 100;
		System.out.println("[2,3]");
		this.debug(numbers, target);
	}

	public void debug6() {
		int[] numbers = { 1, 2, 3, 4, 4, 9, 56, 90 };
		int target = 8;
		System.out.println("[4,5]");
		this.debug(numbers, target);
	}
}
